package link;

/**
 * 单向循环链表（环）
 *  约瑟夫问题
 */
public class CycleLinkList{

    /**
     * 约瑟夫问题:
     *
     *  41个人坐一圈，第一个人编号为1，第二个人为2，第n个人的编号为n。
     * 编号为1的人开始从1报数，依次向后，报数为3的那个人出圈
     * 自退出那个人开始的下一个人再次从1开始报数，以此类推
     * 求最后退出的那个人的编号（最后出圈的人就不用si了）
     */
    public void initJosephus(int n, int k){
        //头结点不存储数据
        Node head = new Node();
        Node cur = head;
        //循环构造这个链表
        for(int i=1;i<=n;i++){
            Node node = new Node(i);
            cur.next = node;
            cur = node;
        }
        //链表有数据的部分首尾相连形成一个环。
        cur.next = head.next;
        //统计开始的时候，刨去头结点，然后从第一个有数据的结点开始报数
        Node p = head.next;
        //循环退出的条件是最后只剩一个结点，也就是这个结点的下一个结点是它本身
        while(p.next!=p){
            //正常报数的遍历逻辑
            for(int i=1;i<k-1;i++){
                p = p.next;//找到要删除的节点的前一个节点
            }
            //当数到3的时候，出局
            System.out.print(p.next.data+"->");
            p.next = p.next.next;
            p = p.next;
        }
        //最后剩下的一个结点
        System.out.println("(left:"+p.data+")");
    }

    /**
     * 节点类
     */
    class Node{
        int data;
        Node next;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }
    }
}
